Հանգույցային տեսակավորում

Հանգույցային տեսակավորումը տեղում, անկայուն տեսակավորման ալգորիթ է, և համեմատական ալգորիթմ է, որը տեսականորեն օպտիմալ է գլխավոր բազմության գրառումների ընդհանուր քանակի համար, ի տարբերություն այլ տեղում տեսակավորման ալգորիթմների։ Այն հիմնաված է այն գաղափարի վրա, տեղափոխությունը, որը պետք է տեսակավորվի, կարեղ է արտացոլվել ցիկլերերով, որը կարող է առանձին պտտվել տեսակավորված արդյունք տալու համար։

Ի տարբերություն համարյա յուրաքանչյուր մնացած ալգորիթմների, անդամները երբեք գրված չեն լինում բազմության մեջ այլ տեղում, պարզապես նրանց ազդեցության ուղուց դուրս հանելու համար։ Յուրաքանչյուր արժեք գրվում է զրո անգամ, եթե այն արդեն իր ճիշտ դիրքում է, կամ գրվում է մեկ անգամ իր ճիշտ դիրքում։ Սա համապատասխանեցնում է գրառումների մինիմալ քանակը, որը պահանջվում է ավարտուն տեղում տեսակավորման համար։

Գրառումների քանակի մինիմալացումը օգտագործվում է, երբ գրառումներն ավելի խոշոր տվյալների բազմություն դարձնելը շատ թանկ է, ինչպես օրինակ EEPROM-ի դեպքում կամ որտեղ որ յուրաքանչյուր գրառում փոքրացնում է հիշողության գոյության տևողությունը, ինչպես օրինակFlash հիշողության դեպքում։

Ալգորիթմ

Հետևյալ ալգորիթմը գտնում և պտտեցնում է ցիկլեր, որոնք տալիս են տեսակավորված արդյունք։ Նշենք, որ range(a, b) գտնվում է a ից b ‑ 1 միջակայքում։

# Sort an array in place and return the number of writes.
def cycleSort(array):
  writes = 0
  
  # Loop through the array to find cycles to rotate.
  for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]
    
    # Find where to put the item.
    pos = cycleStart
    for i in range(cycleStart + 1, len(array)):
      if array[i] < item:
        pos += 1
    
    # If the item is already there, this is not a cycle.
    if pos == cycleStart:
      continue
    
    # Otherwise, put the item there or right after any duplicates.
    while item == array[pos]:
      pos += 1
    array[pos], item = item, array[pos]
    writes += 1
    
    # Rotate the rest of the cycle.
    while pos != cycleStart:
      
      # Find where to put the item.
      pos = cycleStart
      for i in range(cycleStart + 1, len(array)):
        if array[i] < item:
          pos += 1
      
      # Put the item there or right after any duplicates.
      while item == array[pos]:
        pos += 1
      array[pos], item = item, array[pos]
      writes += 1
  
  return writes

Հատուկ իրավիճակների օպտիմալացում

Երբ բազմությունը պարունակում է համեմատաբար փոքր քանակի կրկնօրինակ անդամներ, a հաստատուն ժամանակով կատարյալ քեշ ֆունկցիան կարող է մեծապես արագացնել, թե որտեղ դնել անդամը, որը փոխում է տեսակավորումը Θ(n²)-ից Θ(n + k) անգամ, որտեղ k-ն քեշերի ընդհանուր թիվն է։ Բազմությունը մինչև վերջ տեսակավորվում է քեշերի կարգով, այսպիսով մի քեշ ֆունկցիայի ընտրությունը, որը քեզ տալիս է ճիշտ կարգավորություն, կարևոր է։

Մինչ տեսակավորումը, պետք է ստեղծել հիստոգրամ, տեսակավորված քեշերով, որոնք հաշվում են յուրաքանչյուր քեշի մուտքերի քանակը բազմություն։ Հետո ստեղծվում է աղյուսակ դեպի հիստոգրամ յուրաքանչյուր մուտքի ընդհանուր գումարով։ Ընդհանուր գումարի աղյուսակը այնուհետև պետք է պարունակի յուրաքանչյուր էլեմենտի դիրքը բազմության մեջ։ Էլեմենտների ճիշտ տեղը կարող է գտնվել հաստատուն-ժամանակ քեշավորման և ընդհանուր գումարի փնտրման միջոցով, այլ ոչ թե գծային փնտրումով։